package com.leetcode.partition5;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/28 9:39
 */
public class LC472连接词 {

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        List<String> answer = findAllConcatenatedWordsInADict(s);
        for (String ans : answer) writer.write(ans + " ");
        writer.flush();
    }

    public static List<String> findAllConcatenatedWordsInADict(String[] words) {
        Trie trie = new Trie();
        List<String> answer = new ArrayList<>();
        Arrays.sort(words, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
        //查询每一个单词由几个字典树的节点组成
        for (String word : words) {
            //经过排序的预处理，如果是合成词则会通过简单词递归的拼接查询出来，如果是简单词开始是查询不到的，将它加入到trie中
            if (trie.search(word, 0)) answer.add(word);
            else trie.insert(word);
        }
        return answer;
    }

    private static class Trie {
        private final int N = (int) (1e5 + 10);
        private final int[][] children = new int[N][26];
        private final boolean[] isWord = new boolean[N];
        private int index = 1;

        private void insert(String s) {
            int curr = 0;
            for (int i = 0; i < s.length(); i++) {
                int child = s.charAt(i) - 'a';
                if (children[curr][child] == 0) children[curr][child] = index++;
                curr = children[curr][child];
            }
            isWord[curr] = true;
        }

        private boolean search(String s, int start) {
            if (start > 0 && start == s.length()) return true;
            int curr = 0;
            for (int i = start; i < s.length(); i++) {
                int child = s.charAt(i) - 'a';
                if (children[curr][child] == 0) return false;
                curr = children[curr][child];
                if (isWord[curr] && search(s, i + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
}
